#ifndef _SORT_ALGORITHM_H_
#define _SORT_ALGORITHM_H_ 1

#include <algorithm>
#include <iostream>
#include <vector>

class sort_algorithm
{
  private:
    /* 快速排序哨兵划分 */
    static int partition(std::vector<int> &, int left, int right);
    /* 归并排序合并子数组 */
    static void merge(std::vector<int> &, int, int, int);
    /* 堆排序的从顶至底的堆化 */
    /* size表示堆的大小，index表示要执行堆化的节点的索引 */
    static void sift_down(std::vector<int> &, int size, int index);

  public:
    sort_algorithm() = default;
    ~sort_algorithm() = default;

    static void select_sort(std::vector<int> &array);
    static void bubble_sort(std::vector<int> &array);
    static void insertion_sort(std::vector<int> &array);
    static void quick_sort(std::vector<int> &array, int left, int right);
    static void merge_sort(std::vector<int> &array, int left, int right);
    static void heap_sort(std::vector<int> &array);
    static void bucket_sort(std::vector<int> &array);
    static void counting_sort(std::vector<int> &array);
    static void radix_sort(std::vector<int> &array);
    static void printf_array(const std::vector<int> &array)
    {
        std::cout << "排序结果: ";
        std::for_each(array.cbegin(), array.cend(), [=](int num) { std::cout << num << " "; });
        std::cout << std::endl;
    }
};

#endif